Jag skriver för närvarande en grundläggande parser för en XML-smak. Som en övning implementerar jag en LL-bordsdriven parser. Detta är mitt exempel på BNF-grammatik: % token namn datasträng %% / * LL (1) * / doc: elem elem: "<" open_tag open_tag: namn attr close_tag close_tag: ">" elem_or_data "" | "/>" ; elem_or_data: "<" open_tag elem_or_data | data elem_or_data | / * epsilon * / ; attr: name ":" string attr | / * epsilon * / ; Är denna grammatik korrekt? Varje terminal bokstavlig är mellan citat. De abstrakta terminalerna anges med% token. Jag kodar en handskriven lexer för att konvertera min input till en tokens-lista. Hur skulle jag symbolisera de abstrakta terminalerna?
2021-03-03 08:11:44
Det klassiska tillvägagångssättet skulle vara att skriva ett reguljärt uttryck (eller annan erkännare) för varje möjlig terminal.
Vad du kallar "abstrakta" terminaler, som är helt konkreta, är faktiskt terminaler vars tillhörande mönster känner igen mer än en möjlig inmatningssträng. Strängen som faktiskt känns igen (eller någon beräknad funktion av den strängen) ska skickas till tolkaren som symbolens semantiska värde.
Nominellt kör tokenisern vid varje punkt i inmatningssträngen alla igenkännare och väljer den som har den längsta matchningen. (Detta är den så kallade "maximal munch" -regeln.) Detta kan vanligtvis optimeras, särskilt om alla mönster är reguljära uttryck. (F) lex gör till exempel den optimeringen för dig.
En komplikation i ditt fall är att tokeniseringen av ditt språk är kontextberoende. I synnerhet när målet är elem_or_data är de enda möjliga tokens <,